package br.edu.unifei.mestrado.greedy;

import java.util.ArrayList;
import java.util.Date;
import java.util.List;
import java.util.Scanner;

import org.slf4j.Logger;
import org.slf4j.LoggerFactory;

import br.edu.unifei.mestrado.commons.graph.GraphWrapper;
import br.edu.unifei.mestrado.commons.graph.NodeWrapper;
import br.edu.unifei.mestrado.commons.graph.RelationshipWrapper;
import br.edu.unifei.mestrado.commons.partition.AbstractPartition;
import br.edu.unifei.mestrado.commons.partition.AbstractPartitionIndex;
import br.edu.unifei.mestrado.greedy.util.Partition;
import br.edu.unifei.mestrado.greedy.view.GreedyViewListener;

/*
 * GreedyKWay.c
 *
 *  Created on: Jun 4, 2011
 *      Author: roberto
 */

public abstract class GreedyKWay implements GreedyViewListener {

	private Logger logger = LoggerFactory.getLogger(this.getClass());

	private Partition setHelper = null;

	public void readGraph() {
		getGrafo().readGraph();
	}

	/**
	 * Recupera o objeto grafo especializado.
	 * 
	 * @return
	 */
	protected abstract GraphWrapper getGrafo();
	
	public abstract AbstractPartitionIndex getPartitionIndex();

	/**
	 * Retorna uma aresta wrapper para a aresta verdadeira entre va e vb. Retornar null se não exisistir a
	 * aresta verdadeira.
	 * 
	 * @param va
	 * @param vb
	 * @return
	 */
	public RelationshipWrapper getArestaLinking(NodeWrapper va, NodeWrapper vb) {
		return getGrafo().getArestaLinking(va, vb);
	}

	public Iterable<NodeWrapper> getAllNodes() {
		return getGrafo().getAllNodes();
	}

	public Iterable<RelationshipWrapper> getAllEdges() {
		return getGrafo().getAllEdges();
	}

	/**
	 * Atualiza os valores de N para os nós que ainda não foram escolhidos. <br>
	 * Os nós são visinhos de justPicked, pq ele entrou em algum set então seus visinhos não escolhidos terão
	 * seu N incrementado.
	 * 
	 * //WARN: não funcionou pq um mesmo nó pode ser ???
	 * 
	 * @param justPicked
	 */
	private void updateNForNeighborsOfNode(NodeWrapper justPicked) {
		logger.debug("Atualizando N para os vizinhos do node " + justPicked.getId());
		// UTIL: o subSet é o mesmo do node justPicked.
		SubSet set = setHelper.getSetById(justPicked.getPartition());

		Iterable<RelationshipWrapper> arestas = justPicked.getRelationships();
		for (RelationshipWrapper edge : arestas) {
			NodeWrapper other = edge.getOtherNode(justPicked);
			int partition = other.getPartition();
			if (partition == Partition.NO_PARTITION) {// TODO: rever isso!!!!!!!!!
				// inclui o nó na lista de candidatos para do set
				// visinhos externos
				set.incrementN(other);
				// pega o set onde está a outra ponta
			} else { 
				// UTIL: se a outra ponta já foi usada
				if (partition != set.getId()) { // se a outra ponta está em outra partição, então a aresta está no corte
					setHelper.addEdgeToCut(edge);
//					setHelper.addEdgeToCut(partition, edge);
//					setHelper.addEdgeToCut(set.getId(), edge);
				}
			}
		}
		setHelper.printNForSet(set);
	}

	/**
	 * Atualiza vertices da fronteira.
	 */
	private void updateFrontier(NodeWrapper baseNode) {

		List<NodeWrapper> justIncluded = setHelper.includeNodesToFrontier(baseNode);
		setHelper.printFrontier();

		// UTIL: só recalcula para os nós que estão ligados aos que acabaram de serem incluidos na fronteira.
		// não pode ser todos da fronteira, senão vai incrementar o N novamente, daí fica com N maior que o
		// correto.
		// TODO: não funciona, pq o nó 2 não é atualizado mesmo o nó 7 entrando em S1. E o nó 2 deveria ter
		// seu N incrementado.
		// setHelper.updateNArrayToFrontier(justIncluded);
		updateNForNeighborsOfNode(baseNode);

		setHelper.updateDiffFor();

		// setHelper.printExt();
		// setHelper.printDiff();
	}

	private NodeWrapper peekVertice(int setId, long verticeId) {
		NodeWrapper vertice = getGrafo().getNode(verticeId);
		setHelper.addNodeToSet(setId, vertice);

		vertice.lock();
		vertice.setPartition(setId);

		setHelper.removeFromFrontier(vertice);

		// UTIL: precisa remover o node de todos os sets, e não somente do set que ele foi adicionado
		for (SubSet setTmp : setHelper.getSets().values()) { // sets
			// setHelper.removeNode(setTmp, vertice);
			setTmp.removeNode(vertice);
		}

		// updateNForNeighborsOfNode(vertice);
		return vertice;
	}

	private List<NodeWrapper> chooseVertices(List<Integer> seeds) {
		List<NodeWrapper> vertices = new ArrayList<NodeWrapper>();
		for (int setId = 0; setId < setHelper.getK(); setId++) {
			int verticeId = seeds.get(setId);
			NodeWrapper vertice = peekVertice(setId, verticeId);
			vertices.add(vertice);

			setHelper.addNodeToSet(setId, vertice);
		}
		return vertices;
	}

	/**
	 * Escolhe k vertices iniciais e coloca cada um em um set diferente.
	 */
	private void getSeedVertices(List<Integer> seeds) {
		// chooseRandomVertices(k);
		List<NodeWrapper> vertices = chooseVertices(seeds);
		for (NodeWrapper vertex : vertices) {
			updateFrontier(vertex);
		}
	}

	private SubSet getMinP(int kx) {
		// UTIL: verificar onde faz o setMinval
		// no Bucket.updateDiff
		// no Bucket.calculateMinval

		int avgSubSetSize = 0;
		int sumSubSetSize = 0;
		for (SubSet set : setHelper.getSets().values()) { // sets
			sumSubSetSize += setHelper.getAmountOfNodes(set.getId());
		}
		avgSubSetSize = sumSubSetSize / setHelper.getK();

		SubSet addset = null;
		int minval = Integer.MAX_VALUE;
		for (SubSet set : setHelper.getSets().values()) { // sets
			if (setHelper.getAmountOfNodes(set.getId()) <= avgSubSetSize) {
				Integer min = set.getMinVal();// TODO: verificar se aqui pode vir null
				if (min != null && min < minval) {// pega o minval minimo e seu set
					minval = set.getMinVal();
					addset = set;
				}
			}
		}
		logger.debug("getMinP: Set escolhido: " + addset + " com minVal " + addset.getMinVal());
		return addset;
	}

	/**
	 * Pega o vertice com maior valor de N.
	 * 
	 * @param set
	 * @return
	 */
	private Long getMaxN(SubSet set) {

		// TODO: verificar essa lógica aqui.
		/*
		 * int diff = minValArray[set]; int vertice = bucketArray[set][diff][sizeArray[set][diff]];
		 * deleteVertice(set, vertice); return vertice;
		 */

		// UTIL: usar o diff para pegar o melhor elemento
		int diff = set.getMinVal();
		long escolhido = set.getAnyVerticeWithDiff(diff);

		logger.debug("Vertice escolhido: " + escolhido + " com diff " + diff);
		return escolhido;
	}

	/*
	 * Metodo GreedyKWay.
	 */
	private void executeGreedyKWay(int k, List<Integer> seeds) {
		if (getGrafo().getSizeNodes() > 50) {
			setShowView(false);
			logger.warn("Desabilitando exibição dos do grafo. qtd de vertices > 200");
		}
		
		initView(getGrafo());
		
		long tCalc = 0;
		long tMinP = 0;
		long tMaxN = 0;

		long tIncF = 0;
		long tUpdN = 0;
		long tUpdD = 0;

		long tUpdF = 0;
		long tPicV = 0;
		long tSeed = 0;

		long delta = 0;

		delta = System.currentTimeMillis();
		getGrafo().unlockAllNodes();
		getGrafo().resetPartitionAllNodes();
		long tUnlockReset = System.currentTimeMillis() - delta;
		logger.warn("tUnlockReset: " + tUnlockReset);

		setHelper = new Partition(AbstractPartition.NO_LEVEL, k, getPartitionIndex());
		int remaining = getGrafo().getSizeNodes();
		delta = System.currentTimeMillis();
		getSeedVertices(seeds);
		
		repaint();
		
		tSeed += System.currentTimeMillis() - delta;
		logger.warn("tSeed: " + tSeed);
		remaining -= k;

		while (remaining > 0) {
			if ((remaining % 100) == 0) {
				logger.warn("Nós restantes: " + remaining + " Fronteira: " + setHelper.getFrontierCount());
			}
			delta = System.currentTimeMillis();
			// setHelper.calculateMinvalForAll(frontier.getVertices(), remaining);
			tCalc += System.currentTimeMillis() - delta;

			delta = System.currentTimeMillis();
			SubSet addset = getMinP(k);
			tMinP += System.currentTimeMillis() - delta;

			delta = System.currentTimeMillis();
			Long nodeIdChoosen = getMaxN(addset);
			tMaxN += System.currentTimeMillis() - delta;

			if (nodeIdChoosen == null) {
				logger.warn("Escolheu um vertice null. Verificar. fronteira.size: "
						+ setHelper.getFrontierCount() + " remaining: " + remaining);
				break;
			}
			logger.debug("Adicionando vertice " + nodeIdChoosen + " no set " + addset);

			delta = System.currentTimeMillis();
			NodeWrapper Choosen = peekVertice(addset.getId(), nodeIdChoosen);
			tPicV += System.currentTimeMillis() - delta;

			repaint();

			// delta = System.currentTimeMillis();
			// frontier.includeNodesToFrontier(vertice);
			// tIncF += System.currentTimeMillis() - delta;
			//
			// delta = System.currentTimeMillis();
			// updateNArrayToFrontier();
			// tUpdN += System.currentTimeMillis() - delta;
			//
			// delta = System.currentTimeMillis();
			// updateDiffFor();
			// tUpdD += System.currentTimeMillis() - delta;
			// tUpdF = tIncF + tUpdN + tUpdD;

			delta = System.currentTimeMillis();
			updateFrontier(Choosen);
			tUpdF += System.currentTimeMillis() - delta;

			// TODO: calcular valor do corte

			remaining--;
		}
		logger.warn("Estatisticas: ");
		logger.warn("tCalc: " + tCalc);
		logger.warn("tMinP: " + tMinP);
		logger.warn("tMaxN: " + tMaxN);
		logger.warn("");
		logger.warn("tPicV: " + tPicV);
		logger.warn("tIncF: " + tIncF);
		logger.warn("tUpdN: " + tUpdN);
		logger.warn("tUpdD: " + tUpdD);
		logger.warn("tUpdF: " + tUpdF);

		delta = System.currentTimeMillis();
		int cutWeight = setHelper.getCutWeight();
		long tCut = System.currentTimeMillis() - delta;
		logger.warn("CutWeight: " + cutWeight + " tempo gasto para calcular o cutWeight: " + tCut + " ms.");

		setHelper.printSets();
	}

	public void execute(Integer sets, List<Integer> rawSeeds) {

		int k = -1;
		List<Integer> seeds = null;
		if (sets == null) {
			Scanner sc = new Scanner(System.in);
			while (k < 2 || k > getGrafo().getSizeNodes() / 3) {
				System.out.println("Digite a quantidade de partições (Max " + getGrafo().getSizeNodes() / 3
						+ "): ");
				k = sc.nextInt();
			}
			seeds = readSeeds(k);
		} else {
			k = sets;
			seeds = rawSeeds;
		}
		try {
			getGrafo().beginTransaction();
			readGraph();
			getGrafo().endTransaction();
		} finally {
			getGrafo().finish();
		}

		long time = System.currentTimeMillis();
		try {
			getGrafo().beginTransaction();
			executeGreedyKWay(k, seeds);
			getGrafo().endTransaction();
		} catch (Throwable e) {
			logger.error("Erro executando GreedyKWay.", e);
		} finally {
			getGrafo().finish();
		}
		time = System.currentTimeMillis() - time;
		logger.warn("Fim do GreedyKWay. Tempo gasto: " + time + " ms File: " + getGrafo().getGraphFileName()
				+ " - Hora Termino: " + new Date());
	}

	private List<Integer> readSeeds(int k) {
		List<Integer> seeds = new ArrayList<Integer>();
		Scanner sc = new Scanner(System.in);
		for (int i = 0; i < k; i++) {

			System.out.println("digite o seed " + (i + 1) + ": ");
			int verticeId = sc.nextInt();
			seeds.add(verticeId);
		}
		return seeds;
	}

}